{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## How to solve the [Cheryl's Birthday](https://en.wikipedia.org/wiki/Cheryl's_Birthday) puzzle programmatically.\n",
    "\n",
    "> 1. Albert and Bernard just became friends with Cheryl, and they want to know when her birthday is. Cheryl gave them a list of 10 possible dates:\n",
    "```\n",
    "    May 15     May 16     May 19\n",
    "   June 17    June 18\n",
    "   July 14    July 16\n",
    " August 14  August 15  August 17\n",
    "```\n",
    "1. Cheryl then tells Albert and Bernard separately the month and the day of the birthday respectively.\n",
    "1. Albert: I don't know when Cheryl's birthday is, but I know that Bernard does not know too.\n",
    "1. Bernard: At first I don't know when Cheryl's birthday is, but I know now.\n",
    "1. Albert: Then I also know when Cheryl's birthday is.\n",
    "1. So when is Cheryl's birthday?\n",
    "\n",
    "As with the [pytudes solution](https://github.com/norvig/pytudes/blob/master/ipynb/Cheryl.ipynb), the goal is to solve the puzzle in code.  A different approach is taken here though, for simplicity and extensibility.\n",
    "\n",
    "The first step is to model the data.  A `set` of `Date` objects is suitable to represent the current possible dates.  Since `datetime.date` objects require a year, a minimal `collections.namedtuple` is used instead. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "{August 14,\n August 15,\n August 17,\n July 14,\n July 16,\n June 17,\n June 18,\n May 15,\n May 16,\n May 19}"
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from typing import NamedTuple\n",
    "\n",
    "DATES = ['May 15',    'May 16',    'May 19',\n",
    "        'June 17',   'June 18',\n",
    "        'July 14',   'July 16',\n",
    "      'August 14', 'August 15', 'August 17']\n",
    "\n",
    "class Date(NamedTuple):\n",
    "    month: str\n",
    "    day: str\n",
    "\n",
    "    def __repr__(self):\n",
    "        return ' '.join(self)  # pretty printing\n",
    "DATES = {Date(*date.split()) for date in DATES}\n",
    "DATES"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As is typical of these kinds of puzzles, it assumes all participants have perfect [Theory of Mind](https://en.wikipedia.org/wiki/Theory_of_mind).  That is, each participant making a statement is applying their private knowledge to what is publicly known, and assuming everyone else will do the same.  With that in mind, the claims made fall into 3 categories:\n",
    "* I know ...\n",
    "* I don't know ...\n",
    "* They don't know ...\n",
    "\n",
    "The temporal variations \"now\" and \"at first\" can be modeled by the current set of dates.  Any claim then can be implemented functionally in this form:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def claim(field: str, dates: set) -> set:\n",
    "    \"\"\"Return subset of possible dates which would make the claim true.\n",
    "    \n",
    "    :param field: the field known by the claimant\n",
    "    :param dates: the current set of dates publicly known\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So what does it mean for Albert or Bernard to \"know\" the correct date?  It would mean applying their knowledge of the month or day leaves only one possibility.  The \"I know ...\" function therefore groups and filters for uniqueness."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "{June 18, May 19}"
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import collections\n",
    "\n",
    "def known(field, dates):\n",
    "    \"\"\"Return subset of possible dates which would make the claim \"I know ...\" true.\"\"\"\n",
    "    counts = collections.Counter(getattr(date, field) for date in dates)\n",
    "    return {date for date in dates if counts[getattr(date, field)] == 1}\n",
    "\n",
    "# test what is already publicly known\n",
    "assert known('month', DATES) == set()\n",
    "known('day', DATES)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To implement \"I don't know ...\", `known` could be parametrized with a different predicate (`> 1`), or simply use  `set.difference`.  \"I don't know ...\" is so trivial it's arguably not worth the abstraction."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def unknown(field, dates):\n",
    "    \"\"\"Return subset of possible dates which would make the claim \"I don't know ...\" true.\"\"\"\n",
    "    return dates - known(field, dates)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The challenging part is what does it mean for Albert to claim Bernard doesn't know.  All dates that would be knowable to Bernard must clearly be excluded, but Albert would have to exclude them based on his knowledge of the month.  So \"They don't know ...\" is similar to `unknown`, but the exclusion is based on a different field."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def unknowable(field, dates):\n",
    "    \"\"\"Return subset of possible dates which would make the claim \"They don't know ...\" true.\"\"\"\n",
    "    other, = set(Date._fields) - {field}\n",
    "    exclude = {getattr(date, field) for date in known(other, dates)}\n",
    "    return {date for date in dates if getattr(date, field) not in exclude}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is sufficient to simply walk through the statements, one at a time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "{August 14, August 15, August 17, July 14, July 16}"
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Albert: I don't know when Cheryl's birthday is, but I know that Bernard does not know too.\n",
    "dates = unknown('month', DATES)\n",
    "assert dates == DATES  # already public known\n",
    "dates = unknowable('month', dates)\n",
    "dates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "{August 15, August 17, July 16}"
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Bernard: At first I don't know when Cheryl's birthday is, but I know now.\n",
    "assert dates.isdisjoint(known('day', DATES))  # already claimed by Albert\n",
    "dates = known('day', dates)\n",
    "dates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "{July 16}"
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Albert: Then I also know when Cheryl's birthday is.\n",
    "known('month', dates)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Exactly one date is left, indicating success.  Now the succinct in-lined version, with no superfluous statements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "{July 16}"
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "known('month',                        # Albert: I know\n",
    "    known('day',                      # Bernard: I know\n",
    "        unknowable('month', DATES)))  # Albert: Bernard doesn't know"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "env": {},
   "interrupt_mode": "signal",
   "language": "python",
   "metadata": {},
   "name": "python3"
  },
  "nikola": {
   "category": "puzzles",
   "date": "2018-03-20",
   "description": "",
   "link": "",
   "slug": "cheryls-birthday",
   "tags": "",
   "title": "Cheryl's Birthday",
   "type": "text"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}